1. Field of the Invention
Example embodiments of the present invention relate generally to a method of computing aggregate statistics within a distributed network.
2. Description of the Related Art
Many large-scale distributed applications require aggregate statistics (e.g., MIN, MAX, SUM, RANK, AVERAGE, etc.) to be computed based on data stored at individual nodes. For example, in peer-to-peer (P2P) systems, the average number of files stored at each peer node or the maximum size of files exchanged between nodes can be an important factor for system designers attempting to optimize overall system performance.
Similarly, in sensor networks, disseminating individual readings of temperature or humidity among a plurality of sensor nodes, besides being very expensive, may also be unnecessary, and aggregates like MAX (e.g., a maximum temperature from the plurality of sensor nodes) or AVERAGE (e.g., an average temperature from the plurality of sensor nodes) may be sufficient in most cases.
In another example, in a wireless network monitoring application deploying software probes on mobile handsets to monitor performance, a service provider may be more interested in abnormal measurements recorded by the probes, such as unusually low signal strength or atypically high application response times.
Three important design criteria for aggregate computations are scaling, robustness and communication overhead. Scaling means that the aggregation computation procedure may scale to a large number of nodes (e.g., without prohibitive costs, complexity, resource allocation, etc.). For example, P2P systems and sensor networks may include millions of participating nodes (e.g., distributed throughout the Internet). Accordingly, scaling may refer to how computation times are affected as new nodes join. For example, an aggregate computation procedure with good scaling characteristics may be associated with a linear increase in computation times (e.g., as opposed to an exponential increase) as new nodes are added to the system. Robustness relates to how accurate the aggregate computation remains in the presence of failures at one or more nodes within the system. For example, link and node reliability may be expected to be poor in wireless networks as compared to wired networks. Communication overhead is the signaling or messaging associated with computing the aggregate statistic. For example, wireless communication systems (e.g., IEEE 802.11, Bluetooth, CDMA, OFDMA, GSM, UMTS, etc.) typically have lower bandwidths than wired communication systems, and in wireless sensor networks, nodes have limited battery lives (e.g., which are drained by messaging, searching to establish a connection, etc.).
Accordingly, in order to facilitate computations for aggregate statistics, system designers typically attempt to develop a solution which scales as nodes are added, is robust in the presence of failures and incurs a relatively low communication overhead. However, system designers typically make decisions which “trade-off” between scaling, robustness and communication overhead.
In a conventional centralized aggregate statistic computation process, each of a plurality of nodes within a system (e.g., a P2P system, a sensor system, a wireless system, etc.) transmits a value, to be collected and used in the aggregate statistic computation along with values from other of the plurality of nodes, to a central coordinator. The central coordinator collects the transmitted values and computes the aggregate. The conventional centralized approach is relatively efficient in terms of communication overhead because, assuming n nodes take part in the aggregate statistic computation (i.e., not counting the central coordinator), only n messages require transmission to compute the aggregate statistic. However, the centralized approach is weak in terms of scalability and reliability because the central coordinator may fail (e.g., low robustness) and/or become a bottleneck (e.g., low scalability as more nodes are added).
In a conventional decentralized gossip-based aggregate statistic computation process, each of a plurality of nodes within a system (e.g., a P2P system, a sensor system, a wireless system, etc.) exchanges information with a randomly-selected node within the system during each “round” of the computation process (e.g., a round may be a period of time required to exchange the information used in the computation process). It will be readily appreciated by one of ordinary skill in the art that a gossip-based aggregate statistic computation process has advantages with regard to robustness (e.g., because message failures and/or node failures may be compensated by the random-communication) and scalability as compared to the conventional centralized approach.
FIG. 1 illustrates a conventional decentralized gossip-based aggregate statistic computation process for computing an aggregate AVERAGE. The process of FIG. 1 is performed at each of a plurality of nodes within a system (e.g., a P2P system, a sensor system, a wireless system, etc.), and will hereinafter be described as being performed at a representative Node X. Further, the plurality of nodes will hereinafter be described as including n nodes, where n is a positive integer greater than or equal to 2. The process of FIG. 1 illustrates one “round” of computation, wherein multiple rounds, or iterations, of the process of FIG. 1 are performed at each of the n nodes to compute the aggregate statistic.
In step S100 of FIG. 1, Node X selects one of the n nodes with a well-known random selection algorithm. Node X sends half of a local value to the randomly selected node in step S105. The local value corresponds to the aggregate statistic being computed with the conventional decentralized gossip-based aggregate statistic computation process of FIG. 1. For example, if the aggregate statistic is an average temperature at a plurality of temperature sensors distributed throughout a Heating, Ventilation and Air Conditioning (HVAC) system, the local value referred to in step S105 is the temperature at Node X.
In step S110, the randomly selected node receives half of the local value sent from the Node X. The randomly selected node adds the received value from Node X to half of its own local value in step S115. Thus, a resultant summed value is halfway between previous local values stored at the randomly selected node and the Node x, respectively.
The process of FIG. 1 may be reconfigured to compute other aggregate statistics. For example, each node may send the full amount of its local value to a randomly selected node, and the receiving node may replace its own local value if the received value is lower for MIN, or higher for MAX.
As discussed above, while the process of FIG. 1 is described as performed at Node X and the randomly selected node, the process of FIG. 1 is, in actuality, performed at all n nodes at the same time during each “round”. The process of FIG. 1 repeats a number of times until, statistically, there is a high probability that all n nodes have converged to an approximation of the true, aggregate statistic.
Recent statistical studies have shown that the process of FIG. 1 converges to “true” aggregate statistics at each of the n nodes in (log n) rounds, or iterations, of the process of FIG. 1. Also, because the process of FIG. 1 is performed at each of the n nodes during each round, n multiplied by (log n), or (n log n), messages are sent during the iterative process of FIG. 1.
As discussed above, it is generally undisputed that the conventional decentralized gossip-based aggregate statistic computation process, described above with respect to FIG. 1, is sufficiently robust to handle a reasonable number of node failures throughout the system. Further, (log n) (i.e., a number of rounds to converge to the aggregate statistic) serves as a scalability indicator and (n log n) (i.e., a number of messages throughout the (log n) rounds) serves as a communication overhead indicator for the conventional decentralized gossip-based aggregate statistic computation process.